package link_tree

import (
	"errors"
)

type MTree struct {
	RNode *MNode
}

type MNode struct {
	Data   interface{}
	Index  int64
	Parent *MNode
	LChild *MNode
	RChild *MNode
}

func NewMTree(RNodeData int) *MTree {
	return &MTree{RNode: &MNode{
		Data:RNodeData,
		Index:0,
	}}
}

func (t *MTree) SearchNode(nodeIndex int64) *MNode {
	return t.RNode.SearchNode(nodeIndex)
}

func (t *MTree) AddNode(nodeIndex int64, direction int, node *MNode) bool {
	return t.RNode.AddNode(nodeIndex, direction, node)
}

func (t *MTree) DeleteNode(nodeIndex int64) (*MNode,error) {
	if(nodeIndex<=0){
		return nil, errors.New("root cannot delete")
	}
	return t.RNode.DeleteNode(nodeIndex),nil
}

func (t *MTree) PreOrderTraverseTree() {
	t.RNode.PreOrderTraverseTree()
}

func (t *MTree) InOrderTraverseTree() {
	t.RNode.InOrderTraverseTree()
}

func (t *MTree) PostOrderTraverseTree() {
	t.RNode.PostOrderTraverseTree()
}

func (n *MNode) PreOrderTraverseTree() {
	if (n.Data != nil) {
		println(n.Data.(int))
	} else {
		println("nil")
	}
	if n.LChild != nil {
		n.LChild.PreOrderTraverseTree()
	}
	if n.RChild != nil {
		n.RChild.PreOrderTraverseTree()
	}
}

func (n *MNode) InOrderTraverseTree() {
	if n.LChild != nil {
		n.LChild.InOrderTraverseTree()
	}
	if (n.Data != nil) {
		println(n.Data.(int))
	} else {
		println("nil")
	}
	if n.RChild != nil {
		n.RChild.InOrderTraverseTree()
	}
}

func (n *MNode) PostOrderTraverseTree() {
	if n.LChild != nil {
		n.LChild.PostOrderTraverseTree()
	}
	if n.RChild != nil {
		n.RChild.PostOrderTraverseTree()
	}
	if (n.Data != nil) {
		println(n.Data.(int))
	} else {
		println("nil")
	}
}

func (n *MNode) SearchNode(nodeIndex int64) *MNode {
	if n.Index == nodeIndex {
		return n;
	}
	if n.LChild != nil {
		if n.LChild.Index == nodeIndex {
			return n.LChild
		} else {
			temp := n.LChild.SearchNode(nodeIndex)
			if (temp != nil) {
				return temp
			}
		}
	}
	if (n.RChild != nil) {
		if n.RChild.Index == nodeIndex {
			return n.RChild
		} else {
			temp := n.RChild.SearchNode(nodeIndex)
			if (temp != nil) {
				return temp
			}
		}
	}
	return nil
}

func (n *MNode) AddNode(nodeIndex int64, direction int, node *MNode) bool {
	temp := n.SearchNode(nodeIndex)
	if temp == nil {
		return false
	}
	temp2 := n.SearchNode(node.Index)
	if(temp2 != nil){
		return false
	}
	if direction == 0 {
		temp.LChild = &MNode{
			Data:   node.Data,
			Index:  node.Index,
			Parent: temp,
		}
	} else {
		temp.RChild = &MNode{
			Data:   node.Data,
			Index:  node.Index,
			Parent: temp,
		}
	}
	return true
}

func (n *MNode) DeleteNode(nodeIndex int64) *MNode {
	temp := n.SearchNode(nodeIndex)
	if temp.LChild != nil {
		n.DeleteNode(temp.LChild.Index)
	}
	if temp.RChild != nil {
		n.DeleteNode(temp.RChild.Index)
	}
	if(temp.Parent != nil){
		if temp.Parent.LChild == temp {
			temp.Parent.LChild = nil
		}
		if temp.Parent.RChild == temp {
			temp.Parent.RChild = nil
		}
	}
	rNode := &MNode{
		Data:  temp.Data,
		Index: temp.Index,
	}
	temp = nil;
	return rNode
}
